/*
 * @lc app=leetcode.cn id=234 lang=typescript
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

//  思路：
//  先利用快慢指针找到中点，再反转后半个链表进行比较
//  参考：https://labuladong.github.io/algo/2/18/20/

//  复杂度：O(n)  O(1)

function reverse(head: ListNode | null): ListNode | null {
    let pre = null, curr = head
    while (curr !== null) {
        let next = curr!.next
        curr!.next = pre
        pre = curr
        curr = next
    }
    return pre
}

function isPalindrome(head: ListNode | null): boolean {

    if (!head) return true

    // 找到中间的点 
    let slow: ListNode | null = head, fast: ListNode | null = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow!.next
    }
    if (fast) slow = slow!.next

    let left: ListNode | null = head
    let right: ListNode | null = reverse(slow)

    while (right && left) {
        if (left.val !== right.val) return false
        left = left.next
        right = right.next
    }
    return true
};
// @lc code=end
import { ListNode } from './type'

const l1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))))
const l2 = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))))

console.log(isPalindrome(l1))
console.log(isPalindrome(l2))
